<head>
    <meta charset="UTF-8">
<title>算法训练 数字三角形</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>题目描述</p>
<p>&nbsp;</p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">（图３<span lang="EN-US">.</span>１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路<span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">径，使该路径所经过的数字的总和最大。<span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">　●每一步可沿左斜线向下或右斜线向下走；<span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">　●<span lang="EN-US">1</span>＜三角形行数&le;<span lang="EN-US">100</span>；<span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">　●三角形中的数字为整数<span lang="EN-US">0</span>，<span lang="EN-US">1</span>，&hellip;<span lang="EN-US">99</span>；</span></p>
<p class="MsoNormal">&nbsp;</p>
<p class="MsoNormal">&nbsp;</p>
<p class="MsoNormal"><img src="http://lx.lanqiao.cn/RequireFile.do?fid=9RdAy6Be" width="113" height="123" alt="" />.</p>
<p class="MsoNormal"><span style="font-family: 宋体;">（图３</span><span lang="EN-US" style="font-family: 宋体;">.</span><span style="font-family: 宋体;">１－１）</span></p>
<p>&nbsp;</p>
<p class="MsoNormal">&nbsp;</p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">输入数据：<span lang="EN-US"><o:p></o:p></span></span></p>
<p><span style="font-size:10.5pt;mso-bidi-font-size:10.0pt;font-family:宋体;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;
mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">文件中首先读到的是三角形的行数。</span></p>
<p>&nbsp;</p>
<p class="MsoNormal">接下来描述整个三角形</p>
<p class="MsoNormal">&nbsp;</p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">输出数据：<span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">最大总和（整数）</span></p>
<p class="MsoNormal">样例输入</p>
<p class="MsoNormal">&nbsp;</p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
&quot;Times New Roman&quot;">5<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
&quot;Times New Roman&quot;">7<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
&quot;Times New Roman&quot;">3 8<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
&quot;Times New Roman&quot;">8 1 0<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
&quot;Times New Roman&quot;">2 7 4 4<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
&quot;Times New Roman&quot;">4 5 2 6 5</span></p>
<p class="MsoNormal">样例输出</p>
<p class="MsoNormal">&nbsp;</p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
&quot;Times New Roman&quot;">30<o:p></o:p></span></p>
<p>&nbsp;</p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
&quot;Times New Roman&quot;"><o:p></o:p></span></p>
<p>&nbsp;</p>
<p>&nbsp;</p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;"><span lang="EN-US"><o:p></o:p></span></span></p>
<p>&nbsp;</p>